/*	THINGS TO DO
	input*
	output*
	sort*
	reverse*
	count*
	pop*
	push*
	insert*
	search and delete*
	search*
	
*/

/*
	23/02/11-defined main,new,dis,pus;
	27/02/11-defined sor; edited new,dis;
	02/03/11-defined sea;
	02/03/11-edited func names;defined ins;corrected pus;
	02/03/11-corrected pus;added pop;
	02/03/11-added search and delete;
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

void new();				//New List
void dis();				//Display List
void sor();				//Sort List
void rev();				//Reverse List
int cou(int);				//Count no. of elements
void pop(int);				//Delete last element or parameter position element
void append(int);			//Add element to end of list
void ins(int,int);				//insert into pos
void remov(int);			//search and delete
int ind(int);				//search for position
void extend();

struct node
{
  int i;
  struct node *next;
} *first=NULL,*last=NULL;

int main()
{
  int flag,ch,len,num,pos;
  flag=0;
  ch=300;
  
  while(1)
  {
  printf("\nEnter your choice\n");
  printf("1.New\n2.Display\n3.Sort\n4.Reverse\n5.Count\n6.Pop\n7.Append\n8.Insert\n9.Remove\n10.Index\n11.Extend\n12.Quit\n");
  scanf("%d",&ch);
  if(first==NULL && flag==0 && ch==1)
  {
    flag=1;
  }
  else if(first==NULL && ch>1 && ch<11 && flag==0)
  {
    printf("No existing List !!!");
    continue;
  }
  
  switch(ch)
  {
    case 1:new();break;
    case 2:dis();break;
    case 3:sor();break;
    case 4:rev();break;
    case 5:printf("Count which no. ? : ");scanf("%d",&num);len=cou(num);printf("The count is %d\n\n",len);break;
    case 6:printf("Which Position do you wanna delete ? (-1 deletes last) : ");scanf("%d",&num);pop(num);break;
    case 7:printf("No. to append list with ? : ");scanf("%d",&num);append(num);break;
    case 8:printf("No. to insert ? : ");scanf("%d",&num);printf("Where to insert (position) ? : ");scanf("%d",&pos);ins(num,pos);break;
    case 9:printf("No. to remove ? : ");scanf("%d",&num);remov(num);break;
    case 10:printf("No. to search for ? : ");scanf("%d",&num);pos=ind(num);if(pos!=-1)printf("Found at %d (Index=%d)",pos,pos-1);else printf("Not Found !!!");break;
    case 11:extend();break;
    case 12:exit(0);break;
    default:printf("Choose Wisely ! Live Well...\n");
  }
  }
}

void new()
{
  int num,flag=0;
  char ch='y';
  struct node *n;
  
  while(ch=='y')
  {
    if(flag==0)
    {
      printf("Enter the element : ");
      scanf("%d",&num);
      n=malloc(sizeof(struct node));
      n->i=num;
      n->next=NULL;
      first=n;
      last=n;
      flag=1;
    }
    else
    {
      printf("Enter the element : ");
      scanf("%d",&num);
      n=malloc(sizeof(struct node));
      n->i=num;
      n->next=NULL;
      last->next=n;
      last=n;
    }
    printf("Another one ? (y/n)");
    scanf("%s",&ch);
  }
}

void dis()
{
  struct node *tmp;
  printf("\nThe List is -> ");
  for(tmp=first;tmp!=NULL;tmp=tmp->next)
    printf(" %d",tmp->i);
  printf("\n");
}

void append(int num)
{
  struct node *n;
  n=malloc(sizeof(n));
  n->i=num;
  n->next=NULL;
  if(first==NULL)
  {
    first=n;
    last=first;
  }
  else
  {
   last->next=n;
   last=n;
  }

  dis();
}

void pop(int pos)
{
  struct node *tmp;
  int i;
  
  if(pos==-1)
  {
    for(tmp=first;tmp!=NULL;tmp=tmp->next)
    {
      if(tmp->next==last)
      {
        tmp->next=NULL;
        last=tmp;
        break;
      }
      if(first==last)
      {
        first=NULL;
        last=NULL;
        break;
      }
    }
  }
  else
  {
    for(i=1,tmp=first;tmp!=NULL,i<=pos;i++,tmp=tmp->next)
    {
      if(i==pos-1)
      {
	tmp->next=tmp->next->next;
      }
    }
  }    
  dis();
}

void sor()
{
  struct node *tmp1,*tmp;
  int s,f=0,flag=0;

  for(tmp=first;tmp->next!=NULL;tmp=tmp->next)
  {
    for(tmp1=tmp->next;tmp1!=NULL;tmp1=tmp1->next)
    {
      if((tmp1->i)<(tmp->i))
      {
	s=tmp1->i;
	tmp1->i=tmp->i;
	tmp->i=s;
      }
    }
  }
  printf("After Sorting : ");
  dis();
}

int ind(int num)
{
  int flag=0,pos=1;
  struct node *tmp;
  
  for(tmp=first;tmp!=NULL;tmp=tmp->next)
  {
    if(tmp->i==num)
    {
      flag=1;
      break;
    }
    else
      pos++;
  }
  
  if(flag==0)
    return -1;
  else
    return pos;
}

void ins(int num, int pos)
{
  int c=1;
  struct node *tmp,*n;
  
  n=malloc(sizeof(n));
    
  for(tmp=first;tmp!=NULL;tmp=tmp->next)
  {
    if(pos==1)
    {
      n->i=num;
      n->next=first;
      first=n;
      break;
    }
    else if(pos==c+1)
    {
      n->i=num;
      n->next=tmp->next;
      tmp->next=n;
      break;
    }
    else
      c++;
  }
  dis();
}

void remov(int num)
{

  struct node *tmp;
    
  for(tmp=first;tmp!=NULL;tmp=tmp->next)
  {
   if(tmp!=last)
    {
      if(tmp->next->i==num && tmp->next!=last)
      {
	tmp->next=tmp->next->next;
	break;
      }
      else if(tmp->next->i==num && tmp->next==last)
      {
        tmp->next=tmp->next->next;
        last=tmp;
	break;
      }
    }
    
    if(tmp==first)
      if(first->i==num)
      {
	first=tmp->next;
	break;
      }
   }
  dis();
}
  
int cou(int num)
{
  struct node *tmp;
  int len=0;
  
  for(tmp=first;tmp!=NULL;tmp=tmp->next)
  {
    if(tmp->i==num)
    len++;
  }
  
  return len;
}

void rev()
{
  struct node *tmp=NULL, *p=first, *pb=NULL, *q=NULL;
  while (p!=NULL)
  {
    tmp=p->next;
    p->next=pb;
    pb=p;
    p=tmp;
  }
  first=q;
  first=last;
  last=q;
  dis();
}

void extend()
{
  int num,flag=0;
  char ch='y';
  struct node *n,*f,*l;
  
  printf("Enter secondary List ->\n");
  
  while(ch=='y')
  {
    if(flag==0)
    {
      printf("Enter the element : ");
      scanf("%d",&num);
      n=malloc(sizeof(struct node));
      n->i=num;
      n->next=NULL;
      f=n;
      l=n;
      flag=1;
    }
    else
    {
      printf("Enter the element : ");
      scanf("%d",&num);
      n=malloc(sizeof(struct node));
      n->i=num;
      n->next=NULL;
      l->next=n;
      l=n;
    }
    printf("Another one ? (y/n)");
    scanf("%s",&ch);
  }
  last->next=f;
  last=l;
}